You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi]:
numberOfBoxesiis the number of boxes of typei.numberOfUnitsPerBoxiis the number of units in each box of the typei.
You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.
Return the maximum total number of units that can be put on the truck.
Example 1:
Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4 Output: 8 Explanation: There are: - 1 box of the first type that contains 3 units. - 2 boxes of the second type that contain 2 units each. - 3 boxes of the third type that contain 1 unit each. You can take all the boxes of the first and second types, and one box of the third type. The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
Example 2:
Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10 Output: 91
Constraints:
1 <= boxTypes.length <= 10001 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 10001 <= truckSize <= 106
Average Rating: 4.42 (12 votes)
Solution
Overview
We have to fill the truck with any box type and try to fill in the maximum number of units. The 2D array boxTypes has the following information on each type of box,
- Number of boxes of that type.
- Number of units inside each box of that type.
We must choose the boxes which give us maximum units.
The problem can be implemented using Greedy Approach. We could iteratively fill the truck by picking up the boxes having maximum units from the remaining boxes at every point. Let's look at the approach to implement the problem.
Approach 1: Brute Force
Intuition
We must fill the truck with maximum units. Given the 2D array boxTypes, we could simply traverse over each box type, find the one with maximum units and fill the truck with all the boxes of that type. Once we fill the truck with a box type, we could mark it as used, and again find the box type with maximum units from the remaining ones. This would continue until the truck is not full.
Let the box type with maximum unit be maxUnitsBoxType. The number of boxes that can be put in the truck using boxes of type maxUnitsBoxType is given by maxUnitsBoxType[0].
However, we can only fill the truck until it is not full. That is, we could only put the boxes in the truck until the remaining truck size is greater than 0. Thus, if the remaining space is truck at a certain point is given by, remainingTruckSize, the number of boxes that can be put in the truck can be given by,
boxCount = min(maxUnitsBoxType[0], remainingTruckSize)
Let's understand how can we implement the above idea.
Algorithm
-
Initially, the truck is empty, hence the remaining truck capacity that must be filled would be equal to the truck size. Initialise variable
remainingTruckSizetotruckSize. -
The truck will be filled with boxes one by one until it is not full. In every iteration, we must find a box with maximum units from the remaining box types. Let's use the method
findMaxUnitBoxthat would return the index of a box type with maximum units given bymaxUnitBoxIndexin the 2D array boxTypes. -
Once, we have the
maxUnitBoxIndex, we could find the number of boxes that we could put in the truck as a minimum ofremainingTruckSizeand the number of boxes available of a given type. Calculate the total number of units and reduce the truck's remaining capacity based on the number of boxes put in the truck. -
Also, we must mark the current box as used. One way of doing this would be to simply mark the number of units as
-1. WhenfindMaxUnitBoxwould indicate that all the boxes are already used and we must terminate. -
The process of filling the truck with box types would continue until the truck is not full i.e
remainingTruckSizeis greater than 0.
Implementation
Complexity Analysis
-
Time Complexity : O(n2), where n is the number of elements in array
boxTypes. In the methodfindMaxUnitBox, we are iterating over all the elements in arrayboxTypesto find the maximum units. In the worst case, when all the boxes are added to the truck we would iteratentimes over the array of sizen. This would give total time complexity as O(n2). -
Space Complexity: O(1), as we are using constant extra space to maintain the variables
remainingTruckSizeandunitCount.
Approach 2: Using Array Sort
We could simplify the process of finding the maximum units in every iteration. We could arrange the box types in a particular order such that we could get the desired box type in constant time without having to iterate over the entire array. The simple way to implement this is to sort the array boxTypes in decreasing order of a number of units.
Once all the elements in array boxTypes are sorted in that order, we know that box type at 0th position is the one with maximum units and the one at 1st position having the second highest number of units and so on.
Algorithm
-
Initially, the truck is empty, hence the remaining truck capacity that must be filled would be equal to the truck size. Initialise variable
remainingTruckSizetotruckSize. -
Sort the array
boxTypesin decreasing order of a number of units. -
Start picking up each box type from
boxTypesarray starting from 0th position. The number of boxes that can be put in the truck would be the minimum ofremainingTruckSizeand the number of boxes available of the given type. Calculate the total number of units and reduce the truck's remaining capacity based on the number of boxes put in the truck. -
The process of filling the truck with box types would continue until the truck is not full i.e remainingTruckSize is greater than 0.
The following figure illustrates the approach in detail for truckSize = 8 and boxTypes = [[3, 10], [6, 5], [4, 7], [2, 9]]
Implementation
Complexity Analysis
-
Time Complexity : O(nlogn), where n is the number of elements in array
boxTypes.Sorting the array
boxTypesof sizentakes (nlogn) time. Post that, we iterate over each element in arrayboxTypesand in worst case, we might end up iterating over all the elements in the array. This gives us time complexity as O(nlogn)+O(n)=O(nlogn). -
Space Complexity: O(1), as we use constant extra space.
Approach 3: Using Priority Queue
Intuition
There is yet another way to get the maximum units in constant time by using the Heap data structure. We could build Max Heap where the value at the root node of the heap is always the maximum value among all its children. So we could build a max heap based on the number of units.
In every iteration, we could pick up the box type which is at the root node, and remove it. After removing the root node, the next node with maximum units would become the root bode.
This approach is not an optimization over Approach 2 but just another way to solve the problem.
Algorithm
-
The heap data structure can be implemented using the priority queue. We must specify that the sort order must be based on the number of units in descending order.
-
Initially, the truck is empty, hence the remaining truck capacity that must be filled would be equal to the truck size. Initialise variable
remainingTruckSizetotruckSize. -
The element at the top of the queue is the one having maximum units. Pick that element and remove it from the queue.
-
The number of boxes that can be put in the truck would be the minimum of
remainingTruckSizeand the number of boxes available of a given type. Calculate the total number of units and reduce the truck's remaining capacity based on the number of boxes put in the truck. -
The process of filling the truck with box types would continue until the truck is not full i.e remainingTruckSize is greater than 0.
Implementation
Complexity Analysis
-
Time Complexity : O(nlogn), where n is the number of elements in array
boxTypes.We are adding all the elements of the array
boxTypesin the priority queue, which takes O(n) time.Post that, we would continue iteration until queue is not empty or remaining truck size is greater than 0. In worst case, we might end up iterating n times. Also, removing elements from queue would take (logn) time. This gives us time complexity as O(nlogn)+O(n)=O(nlogn).
-
Space Complexity: O(n), as we use a queue of size n.
January 3, 2021 9:37 AM
Python solution
class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
boxTypes.sort(key=lambda x: -x[1])
cur_size = 0
max_units = 0
for num_box, unit in boxTypes:
max_units += unit * min(truckSize - cur_size, num_box)
cur_size += min(truckSize - cur_size, num_box)
return max_units
January 3, 2021 11:34 PM
You guys forgot the counting sort O(n) time complexity solution:
February 27, 2021 7:05 AM
Java solution:
The first I was thinking about is exactly the Array Sort approach, but I used a while loop inside the for loop to avoid the Minimum comparison. Apparently it too way to long with my solution.
Arrays.sort(boxTypes, (a, b) -> b[1] - a [1]);
int unitCnt = 0;
for (int[] box : boxTypes){
while (truckSize > 0 && box[0] > 0){
unitCnt += box[1];
box[0]--;
truckSize--;
}
}
return unitCnt;
an hour ago
Using a priority queue, shouldn't the complexity be O(k*log(n)) where k is the size of the truck?
5 hours ago
approach 3 is basically the same as 2. but you can get O(nlogk) time complexity by deleting the element while for loop. (k is the average length of pq, in worst case it is n)
It is the same idea with https://leetcode.com/problems/kth-largest-element-in-an-array/
class Solution {
public int maximumUnits(int[][] boxTypes, int truckSize) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[1]-b[1]);
int size = 0;
int totalUnits = 0;
for (int[] box : boxTypes) {
pq.offer(box);
size += box[0];
totalUnits += box[0]*box[1];
while (size - pq.peek()[0] >= truckSize) {
int[] top = pq.poll();
size -= top[0];
totalUnits -= top[0]*top[1];
}
}
if (size <= truckSize) return totalUnits;
return totalUnits - (size - truckSize)*pq.peek()[1];
}
}
June 8, 2021 10:10 PM
In the complexity analysis of the 2nd approach, the additional space complexity is specified as O(1) which is wrong. The sorting step typically uses some variation of the Quicksort algorithm which adds additional space of O(logN).
February 11, 2021 4:31 AM
I used python heap in amazon's OA2 and failed hidden cases.
Last Edit: January 3, 2021 7:31 PM
C# solution
public int MaximumUnits(int[][] boxTypes, int truckSize) {
Array.Sort(boxTypes, (a, b) => {return b[1] - a[1];});
int count = 0;
foreach(var type in boxTypes)
{
int num = Math.Min(type[0], truckSize);
count += num*type[1];
if(truckSize < num)
break;
truckSize -= num;
}
return count;
}
Last Edit: April 17, 2021 4:16 AM
class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
boxTypes = sorted(boxTypes, key=lambda x:x[1], reverse=True)
b = boxTypes
print(b)
l = len(boxTypes)
cap = 0
for i in range(l):
# truckSize = truckSize - b[i][0]
if truckSize > b[i][0]:
cap+=b[i][0]b[i][1]
truckSize = truckSize - b[i][0]
else:
cap+=truckSizeb[i][1]
break
print(cap)
return cap
Last Edit: January 3, 2021 9:39 AM
from operator import itemgetter
class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
lst = sorted(boxTypes, key=itemgetter(1), reverse=True)
i,l,totalUnits, totalBoxes = 0, len(boxTypes), 0, 0
while i < l and totalBoxes < truckSize:
numBoxes, numUnits = lst[i]
print(numBoxes, numUnits)
while numBoxes>0 and totalBoxes < truckSize:
totalUnits+=numUnits
numBoxes-=1
totalBoxes+=1
i+=1
return totalUnits
xxxxxxxxxxclass Solution {public: static bool compare(vector<int>a, vector<int>b) { return a[1] >= b[1]; } int maximumUnits(vector<vector<int>>& boxTypes, int t) { sort(boxTypes.begin(), boxTypes.end(), compare); int res = 0, boxes = 0; for(int i=0;i<boxTypes.size();i++) { if(boxes + boxTypes[i][0] <= t){ boxes += boxTypes[i][0]; res += (boxTypes[i][0]*boxTypes[i][1]); } else { int temp = t - boxes; boxes = t; res += (temp*boxTypes[i][1]); } } return res; }};